The Hough transform is known as a method for efficiently recognizing two-dimensional figures having few changes in shape from within an image. This Hough transform is disclosed in, for example, Non-Patent Document 1 or Patent Document 1. In Non-Patent Document 1, a method is disclosed that recognizes a figure such as a straight line by means of a Hough transform. This method finds a line by modeling a line by two variables that take the radius ρ and angle of rotation Θ as variables, carrying out a voting process using two-dimensional voting space, and then searching for the ρ value and Θ value for which the vote value is a maximum. Non-Patent Document 1 also discloses a method of recognizing circles, which are two-dimensional patterns. When recognizing a circle, a voting space composed of the three variables of the x coordinate and y coordinate of the center point and the radius is used to extract points for which the voting values are maximums. Thus, a Hough transform that uses a single voting space to extract from that space the location for which the vote value is large to find a solution is referred to as a normal Hough transform in the following explanation to distinguish it from the Hough transform that will described hereinbelow.
In addition, a method in which a normal Hough transform is improved to efficiently perform a rotational correction for character recognition is disclosed in Patent Document 1. In Patent Document 1, an image processing device is disclosed that, in order to efficiently find the rotational angle of a character pattern, carries out a coarse-precision Hough transform to determine a coarse-precision angle of distortion, sets a second voting space that is limited to the vicinity of this distortion angle that has been determined and that is more finely demarcated to again carry out a Hough transform, and takes as the solution the detailed distortion angle that is obtained as a result. This method has the advantage of enabling a decrease of the memory resources necessary for holding a voting space compared to preparing one fine-precision voting space to find a solution by a normal Hough transform. In this way, the process of carrying out a coarse-precision Hough transform to first find a coarse-precision solution and then carrying out a detailed-precision Hough transform limited to only the vicinity of the coarse-precision solution to obtain the final solution is referred to as a coarse-fine Hough transform in the following explanation. In addition, regarding the amount of computation that the coarse-precision Hough transform and detailed-precision Hough transform involve, the coarse-precision Hough transform involves a far greater amount of computation when there are only a few two-dimensional patterns that are the objects of recognition in the input image.
FIG. 1 shows a table that summarizes the amount of computation and memory that are required in a normal Hough transform and a coarse-fine Hough transform. Regarding the coarse-fine Hough transform, the amount of computation and the amount of required memory are each shown for the coarse-precision Hough transform and the detailed-precision Hough transform. As shown in FIG. 1, the normal Hough transform is characterized in that it requires an extremely large amount of both computation and memory. The coarse-precision Hough transform of the coarse-fine Hough transform can be regarded as requiring a large amount of computation but a medium amount of memory. The detailed-precision Hough transform is characterized in that it requires a small amount of both computation and memory.
As regards a different technological aspect, hardware that is to be incorporated into an image processing apparatus is described with reference to FIG. 2. Typically, hardware that has been designed specialized for special purposes is frequently used in image processing apparatuses directed to incorporation, but with advances in computer technology, structures are increasingly used in recent years that combine general-purpose processors with programs. These structures can take advantage of software flexibility to enhance various capabilities, and further, have the advantage of decreasing development time and costs because they do not use hardware that consumes a huge amount of development time and that is expensive. A large-capacity memory can also be arranged outside the general-purpose processor to easily realize processing that requires large-capacity memory. However, disadvantage is that the processing speed is slower than dedicated hardware.
Alternatively, another means of realizing an image processing apparatus directed to incorporation in recent years that can be offered is FPGA (Field-Programmable Gate Array) in which, although it is hardware, has a certain degree of flexibility that allows modifying the circuit configuration and the functions via programming. While FPGA has the advantage of extremely fast computation owing to the fact that it is hardware, it also has a limitation in which the capacity of the memory that is provided internally is small. In the case of hardware in which the provided memory is external, data can be sent and received between the FPGA and the external memory, but the slow data read speed from external memory raises the concern that full advantage cannot be taken of the high-speed computing capability of the hardware when reading data from the external memory.